package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


/**
 * @author haomin
 * @date 2022/08/01 10:02
 **/
public class Day17_1_JZ54 {
    // 方法一：迭代法
    public int KthNode1 (TreeNode proot, int k) {
        // write code here
        if(proot == null || k == 0) return -1;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = proot;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            if(!stack.isEmpty()){
                cur = stack.pop();
                if(--k == 0){
                    return cur.val;
                }
            }
            cur = cur.right;
        }
        return -1;
    }

    // 方法二：中序遍历
    List<Integer> list = new ArrayList<>();
    public int KthNode (TreeNode proot, int k) {
        // write code here
        if(proot == null || k == 0) return -1;
        inOrder(proot);
        return k <= list.size() ? list.get(k-1) : -1;
    }
    private void inOrder(TreeNode proot){
        if(proot == null) return;

        inOrder(proot.left);
        list.add(proot.val);
        inOrder(proot.right);
    }
}